package 每日一题;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 1424. 对角线遍历 II
 * 给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：nums = [[1,2,3],
 *              [4,5,6],
 *              [7,8,9]]
 * 输出：[1,4,2,7,5,3,8,6,9]
 * 示例 2：
 *
 *
 *
 * 输入：nums = [[1,2,3,4,5],
 *              [6,7],
 *              [8],
 *              [9,10,11],
 *              [12,13,14,15,16]]
 * 输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
 * 示例 3：
 *
 * 输入：nums = [[1,2,3],
 *              [4],
 *              [5,6,7],
 *              [8],
 *              [9,10,11]]
 * 输出：[1,4,2,5,3,8,6,9,7,10,11]
 * 示例 4：
 *
 * 输入：nums = [[1,2,3,4,5,6]]
 * 输出：[1,2,3,4,5,6]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i].length <= 10^5
 * 1 <= nums[i][j] <= 10^9
 * nums 中最多有 10^5 个数字。
 * 通过次数8,676提交次数21,027
 */
public class D220714_T1424 {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {

        // 相同的一条线上 横坐标+ 纵坐标相等 且横坐标越小排的越靠前
        ArrayList<int[]> arrayList = new ArrayList<>(); //使用数组 定义一个三元组 {i+j,i,value}

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.get(i).size(); j++) {
                arrayList.add(new int[]{i + j, i, nums.get(i).get(j)});
            }
        }

        arrayList.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        int[] result = new int[arrayList.size()];

        for (int i = 0; i < result.length; i++) {
            result[i] = arrayList.get(i)[2];
        }

        return result;
    }
}
